# Copyright (C) 2010 Zajcev Evgeny <zevlg@yandex.ru>

## Algorithm description:
#
# Simple run on the file until there are irregularities.  Yeah that
# simple ;)
#
# Terms:
#   inner node - node that lies inside given polygon
#   inner way  - way with at least one inner node
#   inner relation - relation with at least one of inner node,
#                    way or relation
#   contained node - non-inner node inside inner way
#
# Irregularities:
#   * IRNODE: There may nodes exist that are not checked against
#             ``is_inside()``
#   * IRWAY: There may ways exist that holds inner node
#   * IRREL: There may relations exist that holds inner node or way
# Special irregularities:
#   * IRVER: means that we tracking versions
#   * IRSEEN: means that we track first/last time tag seen positions
#   * SAVING: means that we perform saving
#
# Features:
#   - Handles large files in reasonable time/memory
#   - Handles Extremely Bad Valid OSM (aka eb8) files
#   - Tracks version attribute (last is used, duplicates nuked)
#
# TODO:
#
#   - Handle keyboard interrupt
#   - Track versions correctly
#

__author__ = "Zajcev Evgeny"
__version__ = "0.1"

#cython: boundscheck=False

cimport osmtrunc

include 'osmiip.pxi'
include 'osmxpp.pxi'

import sys, os, time, random
from functools import partial

DEF SAVING = 1
DEF IRNODE = 2
DEF IRWAY  = 4
DEF IRREL  = 8
DEF IRVER  = 16
DEF IRSEEN = 32
DEF IRALL  = IRNODE|IRWAY|IRREL|IRVER|IRSEEN

cdef int IRR[RELATION+1]
IRR[NODE] = IRNODE
IRR[WAY] = IRWAY
IRR[RELATION] = IRREL

cdef int NSPREAD = 50000
cdef int OSPREAD = 10000


# Ad-hoc C-fast array of Python dictionaries
# Cython says that Python objects are not available as elements of
# ordinary C-array.  But using ugly black magic we can get them of
# course.
# Array access is C-fast, dictionary is C-fast, value conversion is
# P-fast, so Osmdict is C-fast by 2/3 factor.
from python cimport PyObject
from python cimport PyDict_SetItem, PyDict_GetItem, PyDict_DelItem
from python cimport PyDict_Contains, PyDict_Size

cdef class Osmdict:
    cdef object _ods
    cdef PyObject* ods[CNODE+1]
    def __init__(self):
        self.empty()

    def empty(self):
        self._ods = []
        for i in range(CNODE+1):
            od = {}
            self.ods[i] = <PyObject*>od
            self._ods.append(od)

    cdef inline bint ismarked(self, int tt, id):
        return PyDict_Contains(<object>self.ods[tt], id)
    cdef inline markval(self, int tt, id):
        cdef PyObject* po = PyDict_GetItem(<object>self.ods[tt], id)
        return <object>po if po else 0
    cdef inline void mark(self, int tt, id, val=1):
        PyDict_SetItem(<object>self.ods[tt], id, val)
    cdef inline void unmark(self, int tt, id):
        PyDict_DelItem(<object>self.ods[tt], id)
    cdef count(self, int tt):
        return PyDict_Size(<object>self.ods[tt])


cdef class Osmtrunc:
    cdef:
        public object stats
        object oi, oo, runum, irregs
        bint v_flag, c_flag
        unsigned int tags_count, regularity
        unsigned long long seen[RELATION+1][2]
        Osmdict marks
        BIO oif, oof
        Polygon spoly

    def __init__(self, oi, oo, Polygon spoly, opts=[]):
        self.oi, self.oo = oi, oo
        self.spoly = spoly

        # Optional flags
        self.c_flag = "-c" in opts
        self.v_flag = "-v" in opts

        self.runum = 0
        self.marks = Osmdict()
        for i in range(RELATION+1):
            self.seen[i][0] = self.seen[i][1] = 0

        # Initial statistics
        self.stats = {"nodes":0, "ways": 0, "relations": 0, "cnodes": 0, \
                      "dups":[set() for i in range(RELATION+1)]}

    def process(self):
        self.stats["run-time"] = 0
        self.oif = BIO(self.oi, "r")

        # Reading/resolving irregularities loop
        self.irregs = [(IRALL, (0, self.oif.filesize))]
        while self.irregs: self.run(self.irregs.pop(0))
        self.show_progress(True)
        if self.v_flag:
            print "+ Reading run done in %f seconds"%self.stats["run-time"]
        if self.marks.count(NODE) == 0:
            self.oif.close()
            if self.v_flag:
                print "- No nodes to save, exiting"
            return

        # Saving run
        self.oof = BIO(self.oo, "w")
        self.oof.save_header(self.spoly, self.oif)
        self.run((SAVING, (0, self.oif.filesize)))
        self.show_progress(True)
        if self.v_flag:
            print "+ Saving run done in %f seconds"% \
                  self.time_diff(str(self.runum))
        self.oof.save_footer()
        self.oof.close();
        self.oif.close()

        # Update stats & release memory
        for k,v in [("nodes", NODE), ("ways", WAY), ("relations", RELATION),
                    ("cnodes", CNODE)]:
            self.stats[k] = self.marks.count(v)
        self.marks.empty()

    def run(self, irreg):
        """Run on the file in hope to resolve IRREG irregularity."""
        self.runum += 1
        rc = str(self.runum)
        self.stats[rc+"-start"] = time.time()

        self.regularity, rlimits = irreg
        self.oif.seek(rlimits[0])
        self.oif.limit = rlimits[1]

        self.tags_count = 0
        self.oif.map_tags(<cbfunc>self.generic_run, self)

        self.stats[rc+"-done"] = time.time()
        self.stats["run-time"] += self.time_diff(rc)

    # generic_run is the place where all the significant job is done
    # try to keep it fast and avoid P-speed as much as possible
    cdef void generic_run(self, tinfo* tag):
        """Process the TAG.
        This procedure is called on each tag found in OSM file."""
        cdef latlon ll
        cdef int spread, tt
        cdef unsigned long long tid
        cdef bint mark, set_mark = False

        # Show sexy progress bar in verbose mode
        if self.v_flag:
            spread = NSPREAD if tag.type is NODE else OSPREAD
            if self.tags_count % spread == 0:
                # Adjust spread for fun
                global NSPREAD, OSPREAD
                adj = random.choice([-1,1])*random.randint(0,spread/3)
                if tag.type is NODE: NSPREAD = 50000 + adj
                else: OSPREAD = 10000 + adj
                self.show_progress()
            self.tags_count += 1

        # Ignore unrecognized tags
        if tag.type > RELATION:
            return

        tid = self.oif.tagattr_id(tag)
        mark = self.marks.ismarked(tag.type, tid)

        # Saving run?
        if self.regularity & SAVING:
            self.save_element(tag, tid, mark)
            return

        # Ignore tag if regular
        if not (self.regularity & IRR[tag.type]):
            return

        if self.regularity & IRVER and mark:
            # Duplicated tag id detected!
            self.stats["dups"][tag.type].add(tid)
            tt = tag.type if mark else CNODE
            ver = self.oif.tagattr_version(tag)
            over = self.marks.markval(tt, tid)
            if over < ver:
                self.marks.mark(tt, tid, ver)

        if tag.type is NODE:
            ll = self.oif.tagattr_latlon(tag)
            if self.spoly.is_inside(ll.lon, ll.lat):
                set_mark = True
                self.add_irregularity(WAY, tag)
                self.add_irregularity(RELATION, tag)
            elif mark:
                # (**) Special case, previous version of the node was
                # inside polygon and new is outside.  Bad situation,
                # but try to handle it via IRWAY
                self.marks.unmark(NODE, tid)
                self.add_irregularity(WAY, tag)
        elif tag.type is WAY:
            if not self.element_is_good(tag):
                if mark:
                    # This is the situation described above (**)
                    # So nuke out this way and all contained nodes
                    # (in case of completeObjects)
                    self.marks.unmark(WAY, tid)
                    if self.c_flag:
                        self.map_itags(tag, <mapifunc>self.way_mn2marker, NULL)
                    self.add_irregularity(RELATION, tag)
            elif not mark:
                # Mark the way and all contained nodes (in case of
                # completeObjects)
                set_mark = True
                if self.c_flag:
                    self.map_itags(tag, <mapifunc>self.way_mn2marker, &set_mark)
                self.add_irregularity(RELATION, tag)

        elif tag.type is RELATION:
            if not self.element_is_good(tag):
                if mark:
                    # Same (**) as for WAY
                    self.marks.unmark(RELATION, tid)
                    self.add_irregularity(RELATION, tag)
            elif not mark:
                set_mark = True
                self.add_irregularity(RELATION, tag)

        # Mark the tag, and store it's version number as mark value
        if not mark and set_mark:
            self.marks.mark(tag.type, tid, self.oif.tagattr_version(tag))
            mark = True

        if self.regularity & IRSEEN:
            # First time visiting tag? notice this
            if not mark and not self.seen[tag.type][0]:
                self.seen[tag.type][0] = self.tag_offset(tag)

            # Set where we've seen tag of this type for the last time
            self.seen[tag.type][1] = self.oif.filesize
            for tt in range(RELATION+1):
                if tt != tag.type and not self.seen[tt][1]:
                    self.seen[tt][1] = self.tag_offset(tag)

    cdef void save_element(self, tinfo* tag, tid, bint mark):
        """Save NODE, WAY or RELATION element represented by TAG."""
        cdef tinfo st
        cdef int tagtype = tag.type

        # Continue if tag is marked or tag is the contained node
        if not mark:
            if tag.type is NODE and self.marks.ismarked(CNODE, tid):
                tagtype = CNODE
                # and continue
            else:
                return

        # Check tag's version
        mv = self.marks.markval(tagtype, tid)
        if mv > self.oif.tagattr_version(tag):
            return

        # Save whole tags if doing completeObjects
        if self.c_flag or tag.type is NODE:
            self.save_tag(tag)
        else:
            # Tag's head
            st.type, st.s, st.e = tag.type, tag.s, tag.h
            self.save_tag(&st)

            # Tag's internals
            if tag.type is WAY:
                st = self.map_itags(tag, <mapifunc>self.way_saver)
            else:
                st = self.map_itags(tag, <mapifunc>self.rel_saver)

            # Tag's tail
            st.e = tag.e
            self.save_tag(&st)

    cdef inline void save_tag(self, tinfo* tag):
        self.oof.save_tag(tag, self.oif)

    cdef bint element_is_good(self, tinfo* tag):
        """Return True if WAY or RELATION element is inner."""
        cdef mapifunc mif
        if tag.type is WAY:
            mif = <mapifunc>self.way_ncounter
        elif tag.type is RELATION:
            mif = <mapifunc>self.rel_mcounter
        else:
            return False

        cdef int nds = 0
        self.map_itags(tag, mif, &nds)
        return nds > 0

    cdef tinfo map_itags(self, tinfo* tag, mapifunc fun, void* udata=NULL):
        """Map FUN by every tag inside TAG.
        If FUN returns True than stop execution."""
        cdef tinfo ndt = self.oif.parse_tag(tag.h, tag.e)
        while ndt.type is not PARTIAL:
            if fun(self, &ndt, udata):
                break
            ndt = self.oif.parse_tag(ndt.e, tag.e)
        return ndt

    # mapifuncs for WAY tag
    cdef bint way_ncounter(self, tinfo* tag, int* cnt):
        """Count marked nodes in the way."""
        if tag.type is ND and \
               self.marks.ismarked(NODE, self.oif.tagattr_ref(tag)):
            cnt[0] += 1
            return True
        return False

    cdef bint way_mn2marker(self, tinfo* tag, void* set):
        """Node (un)marker for completeObjects option."""
        cdef int ref
        if tag.type is ND:
            ref = self.oif.tagattr_ref(tag)
            if set:
                self.marks.mark(CNODE, ref)
            elif self.marks.ismarked(CNODE, ref):
                self.marks.unmark(CNODE, ref)
        return False

    cdef bint way_saver(self, tinfo* tag, void* nu):
        cdef int nid
        if tag.type is not ND:
            self.save_tag(tag)
        else:
            nid = self.oif.tagattr_ref(tag)
            if self.marks.ismarked(NODE, nid) or \
                   self.marks.ismarked(CNODE, nid):
                self.save_tag(tag)
        return False

    # mapifuncs for REL tag
    cdef bint rel_mcounter(self, tinfo* tag, int* cnt):
        if self.rel_mapper(tag, <relfunc>self.member_is_marked):
            cnt[0] += 1
            return True
        return False

    cdef bint rel_saver(self, tinfo* tag, void* nu):
        if tag.type is not MEMBER or \
               self.rel_mapper(tag, <relfunc>self.member_is_marked):
            self.save_tag(tag)
        return False

    cdef bint rel_mapper(self, tinfo* tag, relfunc fun):
        if tag.type is not MEMBER: return False

        cdef char* mtype = self.oif.tagattr_type(tag)
        cdef int mbrtype, mbrid
        if memcmp(mtype, '"node"', 6) == 0:
            mbrtype = NODE
        elif memcmp(mtype, '"way"', 5) == 0:
            mbrtype = WAY
        elif memcmp(mtype, '"relation"', 10) == 0:
            mbrtype = RELATION
        else:
            return False

        mbrid = self.oif.tagattr_ref(tag)
        return fun(self, tag, mbrtype, mbrid)

    cdef bint member_is_marked(self, tinfo* nu, int mt, int id):
        return self.marks.ismarked(mt, id)

    cdef unsigned long long tag_offset(self, tinfo* tag):
        return self.oif.progress + (tag.s-self.oif.buff)

    cdef void add_irregularity(self, int tp, tinfo* tag):
        if self.seen[tp][0]:
            toff = self.tag_offset(tag)
            self.irregs = [reduce(irregs_sum, self.irregs, \
                                  (IRR[tp], (self.seen[tp][0], toff)))]
            # Force scaning to the end of seen
            if self.oif.limit < self.seen[tp][1]:
                self.oif.limit = self.seen[tp][1]

    # Utility methods
    def time_diff(self, code):
        return self.stats[code+'-done'] - self.stats[code+'-start']

    def show_progress(self, done=False):
        """Show progress bar for current run."""
        if not self.v_flag: return
        if self.regularity & SAVING:
            title = "Saving"
        else:
            title = "Reading%d"%self.runum
        pl = 40 - len(title)
        prg = pl if done else pl*self.oif.progress/self.oif.filesize
        prgs = "="*prg + ">" + "."*(pl-prg)
        rstr = "\r+ %s run: [%s] %d tags"%(title, prgs, self.tags_count)
        if len(rstr) < 77: rstr += " "*(77-len(rstr))
        if done: rstr += "\n"
        sys.stdout.write(rstr)
        sys.stdout.flush()

# Yet no lambdas in Cython
def irregs_sum(i, n):
    i1, n1 = i[1], n[1]
    return (i[0]|n[0],(min(i1[0],n1[0]),max(i1[1],n1[1])))
